package com.chj.gaoji.class15;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Code02_SlidingWindowMedian {

	public static class SBTNode<K extends Comparable<K>> {
		public K key;
		public SBTNode<K> l;
		public SBTNode<K> r;
		public int size;

		public SBTNode(K k) {
			key = k;
			size = 1;
		}
	}

	public static class SizeBalancedTreeMap<K extends Comparable<K>> {
		private SBTNode<K> root;

		private SBTNode<K> rightRotate(SBTNode<K> cur) {
			SBTNode<K> leftNode = cur.l;
			cur.l = leftNode.r;
			leftNode.r = cur;
			leftNode.size = cur.size;
			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
			return leftNode;
		}

		private SBTNode<K> leftRotate(SBTNode<K> cur) {
			SBTNode<K> rightNode = cur.r;
			cur.r = rightNode.l;
			rightNode.l = cur;
			rightNode.size = cur.size;
			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
			return rightNode;
		}

		private SBTNode<K> matain(SBTNode<K> cur) {
			if (cur == null) {
				return null;
			}
			if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
				cur = rightRotate(cur);
				cur.r = matain(cur.r);
				cur = matain(cur);
			} else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
				cur.l = leftRotate(cur.l);
				cur = rightRotate(cur);
				cur.l = matain(cur.l);
				cur.r = matain(cur.r);
				cur = matain(cur);
			} else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
				cur = leftRotate(cur);
				cur.l = matain(cur.l);
				cur = matain(cur);
			} else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
				cur.r = rightRotate(cur.r);
				cur = leftRotate(cur);
				cur.l = matain(cur.l);
				cur.r = matain(cur.r);
				cur = matain(cur);
			}
			return cur;
		}

		private SBTNode<K> findLastIndex(K key) {
			SBTNode<K> pre = root;
			SBTNode<K> cur = root;
			while (cur != null) {
				pre = cur;
				if (key.compareTo(cur.key) == 0) {
					break;
				} else if (key.compareTo(cur.key) < 0) {
					cur = cur.l;
				} else {
					cur = cur.r;
				}
			}
			return pre;
		}

		private SBTNode<K> add(SBTNode<K> cur, K key) {
			if (cur == null) {
				return new SBTNode<K>(key);
			} else {
				cur.size++;
				if (key.compareTo(cur.key) < 0) {
					cur.l = add(cur.l, key);
				} else {
					cur.r = add(cur.r, key);
				}
				return matain(cur);
			}
		}

		private SBTNode<K> delete(SBTNode<K> cur, K key) {
			cur.size--;
			if (key.compareTo(cur.key) > 0) {
				cur.r = delete(cur.r, key);
			} else if (key.compareTo(cur.key) < 0) {
				cur.l = delete(cur.l, key);
			} else {
				if (cur.l == null && cur.r == null) {
					// free cur memory -> C++
					cur = null;
				} else if (cur.l == null && cur.r != null) {
					// free cur memory -> C++
					cur = cur.r;
				} else if (cur.l != null && cur.r == null) {
					// free cur memory -> C++
					cur = cur.l;
				} else {
					SBTNode<K> pre = null;
					SBTNode<K> des = cur.r;
					des.size--;
					while (des.l != null) {
						pre = des;
						des = des.l;
						des.size--;
					}
					if (pre != null) {
						pre.l = des.r;
						des.r = cur.r;
					}
					des.l = cur.l;
					des.size = des.l.size + (des.r == null ? 0 : des.r.size) + 1;
					// free cur memory -> C++
					cur = des;
				}
			}
			return cur;
		}

		private SBTNode<K> getIndex(SBTNode<K> cur, int kth) {
			if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
				return cur;
			} else if (kth <= (cur.l != null ? cur.l.size : 0)) {
				return getIndex(cur.l, kth);
			} else {
				return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
			}
		}

		public int size() {
			return root == null ? 0 : root.size;
		}

		public boolean containsKey(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			SBTNode<K> lastNode = findLastIndex(key);
			return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
		}

		public void add(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			SBTNode<K> lastNode = findLastIndex(key);
			if (lastNode == null || key.compareTo(lastNode.key) != 0) {
				root = add(root, key);
			}
		}

		public void remove(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			if (containsKey(key)) {
				root = delete(root, key);
			}
		}

		public K getIndexKey(int index) {
			if (index < 0 || index >= this.size()) {
				throw new RuntimeException("invalid parameter.");
			}
			return getIndex(root, index + 1).key;
		}

	}

	public static class Node implements Comparable<Node> {
		public int index;
		public int value;

		public Node(int i, int v) {
			index = i;
			value = v;
		}

		@Override
		public int compareTo(Node o) {
			return value != o.value ? Integer.valueOf(value).compareTo(o.value)
					: Integer.valueOf(index).compareTo(o.index);
		}
	}

	public static double[] medianSlidingWindow(int[] nums, int k) {
		SizeBalancedTreeMap<Node> map = new SizeBalancedTreeMap<>();
		for (int i = 0; i < k - 1; i++) {
			map.add(new Node(i, nums[i]));
		}
		double[] ans = new double[nums.length - k + 1];
		int index = 0;
		for (int i = k - 1; i < nums.length; i++) {
			map.add(new Node(i, nums[i]));
			if (map.size() % 2 == 0) {
				Node upmid = map.getIndexKey(map.size() / 2 - 1);
				Node downmid = map.getIndexKey(map.size() / 2);
				ans[index++] = ((double) upmid.value + (double) downmid.value) / 2;
			} else {
				Node mid = map.getIndexKey(map.size() / 2);
				ans[index++] = (double) mid.value;
			}
			map.remove(new Node(i - k + 1, nums[i - k + 1]));
		}
		return ans;
	}

	public static double[] medianSlidingWindow02(int[] nums, int k) {
		double[] medians = new double[nums.length - k + 1];
		Map<Integer, Integer> hashTable = new HashMap<>();
		for (int i = 0; i < medians.length; i++) {
			hashTable.put(nums[i], 0);
		}

		PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.compareTo(o1);
			}

		});

		PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o1.compareTo(o2);
			}

		});

		int i = 0; // index of current incoming element being processed

		// initialize the heaps
		while (i < k) {
			maxHeap.add(nums[i++]);
		}
		for (int j = 0; j < k / 2; j++) {
			minHeap.add(maxHeap.peek());
			maxHeap.poll();
		}

		int index = 0;
		while (true) {
			// get median of current window
			medians[index++] = (k & 1) > 0 ? maxHeap.peek() : ((double) maxHeap.peek() + (double) minHeap.peek()) * 0.5;

			if (i >= nums.length)
				break; // break if all elements processed

			int out_num = nums[i - k]; // outgoing element
			int in_num = nums[i++]; // incoming element
			int balance = 0; // balance factor

			// number `out_num` exits window
			balance += (out_num <= maxHeap.peek() ? -1 : 1);
			hashTable.put(out_num, hashTable.get(out_num) + 1);

			// number `in_num` enters window
			if (!maxHeap.isEmpty() && in_num <= maxHeap.peek()) {
				balance++;
				maxHeap.add(in_num);
			} else {
				balance--;
				minHeap.add(in_num);
			}

			// re-balance heaps
			if (balance < 0) { // `maxHeap` needs more valid elements
				maxHeap.add(minHeap.peek());
				minHeap.poll();
				balance++;
			}
			if (balance > 0) { // `minHeap` needs more valid elements
				minHeap.add(maxHeap.peek());
				maxHeap.poll();
				balance--;
			}

			// remove invalid numbers that should be discarded from heap tops
			while (!maxHeap.isEmpty() && hashTable.containsKey(maxHeap.peek()) && hashTable.get(maxHeap.peek()) > 0) {
				int removeNum = maxHeap.poll();
				hashTable.put(removeNum, hashTable.get(removeNum) - 1);
			}
			while (!minHeap.isEmpty() && hashTable.containsKey(minHeap.peek()) && hashTable.get(minHeap.peek()) > 0) {
				int removeNum = minHeap.poll();
				hashTable.put(removeNum, hashTable.get(removeNum) - 1);
			}
		}

		return medians;
	}

	public static void main(String[] args) {
		{
			int[] nums = { 1, 3, -1, -3, 5, 3, 6, 7 };
			int k = 3;
			double[] ans = medianSlidingWindow(nums, k);
			System.out.println(ans);
		}
//		[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
		{
			int[] nums = { 1, 3, -1, -3, 5, 3, 6, 7 };
			int k = 3;
			double[] ans = medianSlidingWindow02(nums, k);
			System.out.println(ans);
		}
//		[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
	}

}

//class Solution {
//    public static double[] medianSlidingWindow(int[] nums, int k) {
//        if (nums == null || nums.length == 0) {
//            return new double[]{};
//        }
//        double[] res = new double[nums.length - k + 1];
//        PriorityQueue<Double> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
//        PriorityQueue<Double> minHeap = new PriorityQueue<>();
//        //滑动窗口固定写法
//        int i = 0, j = 0;
//        int count = 0;
//        int index = 0;  //res的下标
//        for (i = 0; i < nums.length - k + 1; i++) {
//            while (j < nums.length && count < k) {
//                add(maxHeap, minHeap, nums[j]);
//                count++;
//                j++;
//            }
//            if (count == k) {
//                if (maxHeap.size() == minHeap.size()) {
//                    res[index++] = (maxHeap.peek() + minHeap.peek()) * 0.5;     //这边给[2147483647,2147483647]，这就越界了，用long～
//                } else {
//                    res[index++] = maxHeap.peek();
//                }
//            }
//            count--;
//            remove(maxHeap, minHeap, (double)nums[i]);
//        }
//        return res;
//    }
//
//    public static void add(PriorityQueue<Double> maxHeap, PriorityQueue<Double> minHeap, double num) {
//        maxHeap.offer((double)num);
//        minHeap.offer(maxHeap.poll());
//        if (minHeap.size() > maxHeap.size()) {
//            maxHeap.offer(minHeap.poll());
//        }
//        return;
//    }
//
//    public static void remove(PriorityQueue<Double> maxHeap, PriorityQueue<Double> minHeap, double del) {
//        if (del <= maxHeap.peek()) {
//            maxHeap.remove(del);
//        } else {
//            minHeap.remove(del);
//        }
//        return;
//    }
//}
//
//
//作者：jerry_nju
//链接：https://leetcode-cn.com/problems/sliding-window-median/solution/dui-295ti-shao-zuo-gai-jin-by-jerry_nju/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
